#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/23 22:00
# @USER    : Shengji He
# @File    : xSqrt.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


class Solution:
    def mySqrt(self, x: int) -> int:
        """
        Implement int sqrt(int x).

        Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

        Since the return type is an integer, the decimal digits are truncated and only the integer part of the
        result is returned.

        Example 1:
            Input: 4
            Output: 2

        Example 2:
            Input: 8

            Output: 2

            Explanation: The square root of 8 is 2.82842..., and since
                         the decimal part is truncated, 2 is returned.

        :param x:
        :return:
        """
        if x == 0:
            return 0
        C = x0 = x
        while True:
            xi = 0.5 * (x0 * x0 + C) / x0
            if abs(x0 - xi) < 1e-5:
                break
            x0 = xi
        return int(x0)


if __name__ == '__main__':
    S = Solution()
    x = 18
    print(S.mySqrt(x))
    print('done')
